High Efficiency Video Coding (HEVC) is a new coding standard that has been developed in recent years. In the High Efficiency Video Coding (HEVC) system, the fixed-size macroblock of H.264/AVC is replaced by a flexible block, named coding unit (CU). Pixels in the CU share the same coding parameters to improve coding efficiency. A CU may begin with a largest CU (LCU), which is also referred as coded tree unit (CTU) in HEVC. In addition to the concept of coding unit, the concept of prediction unit (PU) is also introduced in HEVC. Once the splitting of CU hierarchical tree is done, each leaf CU is further split into one or more prediction units (PUs) according to prediction type and PU partition.
Along with the High Efficiency Video Coding (HEVC) standard development, the development of extensions of HEVC has also started. The HEVC extensions include range extensions (RExt) which target at non-4:2:0 color formats, such as 4:2:2 and 4:4:4, and higher bit-depths video such as 12, 14 and 16 bits per sample. One of the likely applications utilizing RExt is screen sharing, over wired- or wireless-connection. Due to specific characteristics of screen contents, coding tools have been developed and demonstrate significant gains in coding efficiency. Among them, the palette coding (a.k.a. major color based coding) techniques represent block of pixels using indices to the palette (major colors), and encode the palette and the indices by exploiting spatial redundancy. While the total number of possible color combinations is huge, the number of colors in an area of picture is usually very limited for typical screen contents. Therefore, the palette coding becomes very effective for screen content materials.
During the early development of HEVC range extensions (RExt), several proposals have been disclosed to address palette-based coding. For example, a palette prediction and sharing technique is disclosed in JCTVC-NO247 (Guo et al., “RCE3: Results of Test 3.1 on Palette Mode for Screen Content Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 14th Meeting: Vienna, AT, 25 July-2 Aug. 2013 Document: JCTVC-NO247). In JCTVC-NO247, the palette of each color component is constructed and transmitted. The palette can be predicted (or shared) from its left neighboring CU to reduce the bitrate. A pseudo code for the method disclosed in JCTVC-NO247 is shown as follows.
For (color_index)  If (palette_pred[color_index])   Current CU palette[color_index] = left CU palette[color_index]  Else   Parse syntax for the palette[color_index] of the current CU  EndEnd
As shown in the pseudo code above, when the palette prediction mode is used as indicated by palette_pred[color_index], the palette for the current coding unit having color_index (i.e., Current CU palette[color_index]) is shared from the palette of the CU having the same color_index at the left side of the current CU (i.e., left CU palette[color_index]). Otherwise, a new palette is parsed from the bitstream at the decoder side or signaled in the bitstream at the encoder side. The method according to JCTVC-NO247 does not use palette prediction (sharing) from the above CU. Furthermore, if the left CU is not coded using palette mode, the palette for the current CU cannot be predicted from the left CU.
Another palette coding method is disclosed in JCTVC-NO249 (Guo et al., “non-RCE3: Modified Palette Mode for Screen Content Coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 14th Meeting: Vienna, AT, 25 July-2 Aug. 2013 Document: JCTVC-NO249). In JCTVC-NO249, each element in the palette is a triplet, representing a specific combination of the three color components.
Yet another palette coding is disclosed in JCTVC-O0182 (Guo et al., “AHG8. Major-color-based screen content coding”, Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 15th Meeting: Geneva, CH, 23 Oct.-1 Nov. 2013, Document: JCTVC-O0182). In JCTVC-O0182, each component is constructed and transmitted. However, instead of predicting the entire palette from the left CU, individual entry in a palette can be predicted from the exact corresponding palette entry in the above CU or left CU. A pseudo code for the method disclosed in JCTVC-O0182 is shown as follows.
For (color_index)  Parse syntax num_major_color[color_index]  For (n <= num_major_color[color_index])    If (palette_pred[color_index][n])      If (pred_from_above[color_index][n])        Current CU palette[color_index][n] = Above CU        palette[color_index][n]      Else        Current CU palette[color_index][n] = Left CU        palette[color_index][n]      End    Else      Parse syntax for current CU palette[color_index][n]    End   EndEnd
As shown in the above pseudo code, the individual entry n of the palette for the current CU (i.e., Current CU palette[color_index][n] for order position n) may be shared from the corresponding palette entry of the above CU (i.e., Above CU palette[color_index][n]) or the left CU (i.e., Left CU palette[color_index][n]) when palette prediction is selected as indicated by palette_pred[color_index][n] being 1. If the palette prediction is not used as indicated by palette_pred[color_index][n] being 0, the palette for the current CU is parsed from the bitstream (i.e., Parse syntax for current CU palette[color_index][n]) at the decoder side or signaled in the bitstream at the encoder side.
As shown above, the palette coding according to JCTVC-O0182 uses element-by-element (or entry-by-entry) predictive coding. Therefore, the parsing complexity (multiple levels) becomes high. Furthermore, it may not be very efficient since palette elements (palette entries) in adjacent CUs might not be at same order position n, even if they have the same value.
Therefore, it is desirable to develop methods for further improving the coding efficiency and/or reducing the complexity associated with the palette coding.